1. Technical Field
The present invention relates in general to data processing and, in particular, to an improved indexed table for a data processing system. In some embodiments, the indexed table can be implemented in a branch prediction table.
2. Description of the Related Art
A state-of-the-art microprocessor can comprise, for example, a cache for storing instructions and data, an instruction sequencing unit for fetching instructions from the cache, ordering the fetched instructions, and dispatching the fetched instructions for execution, one or more sequential instruction execution units for processing sequential instructions, and a branch processing unit (BPU) for processing branch instructions.
Branch instructions processed by the BPU can be classified as either conditional or unconditional branch instructions. Unconditional branch instructions are branch instructions that change the flow of program execution from a sequential execution path to a specified target execution path and which do not depend upon a condition supplied by the occurrence of an event. Thus, the branch specified by an unconditional branch instruction is always taken. In contrast, conditional branch instructions are branch instructions for which the indicated branch in program flow may be taken or not taken depending upon a condition within the processor, for example, the state of specified condition register bit(s) or the value of a counter.
Conditional branch instructions can be further classified as either resolved or unresolved based upon whether or not the condition upon which the branch depends is available when the conditional branch instruction is evaluated by the BPU. Because the condition upon which a resolved conditional branch instruction depends is known prior to execution, resolved conditional branch instructions can typically be executed and instructions within the target execution path fetched with little or no delay in the execution of sequential instructions. Unresolved conditional branches, on the other hand, can create significant performance penalties if fetching of sequential instructions is delayed until the condition upon which the branch depends becomes available and the branch is resolved.
Therefore, in order to minimize execution stalls, some processors speculatively predict the outcomes of unresolved branch instructions as taken or not taken. Utilizing the result of the prediction, the instruction sequencing unit is then able to fetch instructions within the speculative execution path prior to the resolution of the branch, thereby avoiding a stall in the execution pipeline in cases in which the branch is subsequently resolved as correctly predicted. Conventionally, prediction of unresolved conditional branch instructions has been accomplished utilizing static branch prediction, which predicts resolutions of branch instructions based upon criteria determined prior to program execution, or utilizing dynamic branch prediction, which predicts resolutions of branch instructions by reference to branch history accumulated on a per-address basis within a branch history table (BHT) and/or branch target address cache (BTAC).
One problem to which indexed tables such as BHTs are susceptible is aliasing. Aliasing occurs when different elements having differing associated resources map to the same table entry. For example, in the case of a BHT, aliasing occurs when two different branch instruction addresses (BIAs) having different branch outcomes share a common index portion. Based upon the common index portion of the BIAs, the two BIAs will both map to a same BHT entry, which can lead to an incorrect prediction for one or both BIAs.
In many cases, decreasing aliasing in an indexed table by increasing the number of bits utilized to index into the table is not practical in that the addition of one additional index bit doubles the size of the indexed table. Even so, increasing the number of indexed bits does not guarantee elimination of aliasing because in some cases addresses (or other bit strings utilized as resource identifiers) only differ in their higher-order bits. In such cases, increasing the number of index bits, which are typically drawn from the more variable lower-order bits of an address, may not eliminate aliasing.